package test3;

import apple.laf.JRSUIUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution2 {

    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode node = null;
        TreeNode root2 = null;
        TreeNode node2 = root;
        while (root.left != null) {
            root = root.left;
        }
        while (node2 != null) {
            if (node2.left != null) {
                node = node2;
                node2 = node2.left;
                root2 = node2;
                while (node2.right != null) {
                    node2 = node2.right;
                }
                node2.right = node;
                node.left = null;
                node2 = root2;
            } else {
                root2 = node2;
                node2 = node2.right;
                node = node2;
                if (node2 != null) {
                    while (node2.left != null) {
                        node2 = node2.left;
                    }
                    root2.right = node2;
                    node2=node;
                }

            }
        }
        return root;
    }
    public static TreeNode increasingBST2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = increasingBST2(root.left);
        TreeNode right = increasingBST2(root.right);
        if (left == null) {
            root.right = right;
            print(root);
            System.out.println("中间输出");
            print(right);
            System.out.println("中间的右边");
            return root;
        } else {
            TreeNode node = left;
            while (node.right != null) {
                node = node.right;
            }
            node.right = root;
            root.right = right;
            root.left = null;

            print(left);

            System.out.println("左边输出");
            return left;
        }

    }

    public boolean hasPathSum(TreeNode root, int sum) {

        if (root == null) {
            return false;
        }
        if (sum < 0) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }
        boolean left = hasPathSum(root.left, sum - root. val);
        boolean right = hasPathSum(root.right, sum - root. val);
        if (left || right) {
            return true;
        }
        return false;
    }


    public static void print (TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return;
        }
        print(root.left);
        System.out.print(root.val + ", ");
        print(root.right);
    }

    public static void print2 (TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        TreeNode node = root.left;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.add(node);
                node = node.left;
            } else {
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }
        System.out.println(result);
    }

    public static void print3 (TreeNode root) {
        if (root == null) {
            return;
        }
        ArrayList<Integer> result = new ArrayList<>();
        TreeNode node = null;
        while (root != null) {
            if (root.left == null) {
                node = root;
                while (node.right != null ) {
                    node = node.right;
                }
                if (node != root) {
                    node.right = root;
                }

                result.add(root.val);
                root = root.right;

            } else {
                root = root.left;
                node = root;
                result.add(root.val);
            }
        }
        System.out.println(result);
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(8);
        root.right.right.left = new TreeNode(7);
        root.right.right.right = new TreeNode(9);

        print2(root);

        /*System.out.println("");
        System.out.println("--------------------");
        TreeNode node = increasingBST2(root);
        print(node);
*/

    }
}
 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
